/**
         *  思路： 这里每一个数字只要不是0都会对应一个字符，如果是两个数字的话必须小于等于26才 能对应一个字符（并且不能有前导0）。
         *        所以这题的解题思路就有了，就是把字符串不 停的拆开，要么拆一个要么拆两个，所以大家很容易想到的就是二叉树，我们随便举个 例子画个图来看一下。
         *
         *
         * */

function numDecodings(s) {
    return binaryTreeTraversal(s.split(""), s.length, 0);
}

// 优化前：
// 如果找到一种方法返回1，如果没有找到返回 0
function binaryTreeTraversal(chars, len, index) {
    // 如果都遍历完了
    if (index >= len) {
        return 1;
    }
    // 如果当前位置是 0 不合法
    if (chars[index] === "0") {
        return 0;
    }
    // 挪动一位的情况
    var res = binaryTreeTraversal(chars, len, index + 1);

    if (
        index < len - 1 &&
        (chars[index] === "1" ||
            (chars[index] === "2" && chars[index + 1] <= "6"))
    ) {
        // 挪动两位
        res += binaryTreeTraversal(chars, len, index + 2);
    }

    return res;
}

// 运行上面代码的时候我们发现当数据量比较大的时候直接超时，这是因为上面代码中包 含了大量的重复计算
function numDecodings(s) {
    const map = new Map();
    return binaryTreeTraversal(s.split(""), s.length, map, 0);
}
// 优化后：
function binaryTreeTraversal(chars, len, map, index) {
    if (index >= len) {
        return 1;
    }
    if (map.get(index)) {
        return map.get(index);
    }
    // 如果当前位置是 0 不合法
    if (chars[index] === "0") {
        return 0;
    }
    var res = binaryTreeTraversal(chars, len, map, index + 1);

    if (
        index < len - 1 &&
        (chars[index] === "1" ||
            (chars[index] === "2" && chars[index + 1] <= "6"))
    ) {
        res += binaryTreeTraversal(chars, len, map, index + 2);
    }
    map.set(index, res);
    return res;
}